<html>
 <head>
  <meta charset="UTF-8">
 </head>
 <body>
  <h1 data-lake-id="MZBuf" id="MZBuf"><span data-lake-id="ubd19f74a" id="ubd19f74a">典型回答</span></h1>
  <p data-lake-id="u4a7c23d5" id="u4a7c23d5"><br></p>
  <p data-lake-id="u42226e8b" id="u42226e8b"><span data-lake-id="u5fd2fc21" id="u5fd2fc21">B树（B- Tree）和B+树（B+ Tree）是两种常用的树结构，B是Balanced首字母，平衡的意思，他们经常用在各种数据库中，比如MySQL的InnoDB引擎使用的就是B+树，而MongoDB使用的就是B树存储。</span></p>
  <p data-lake-id="ued0c1ad3" id="ued0c1ad3"><span data-lake-id="u30c4aa9e" id="u30c4aa9e">​</span><br></p>
  <p data-lake-id="ub155d4fc" id="ub155d4fc"><span data-lake-id="uf3c13640" id="uf3c13640">B树属于多叉树又名平衡多路查找树，B树的设计目的是为了减少磁盘访问次数，提高查询性能。</span></p>
  <p data-lake-id="u2ea997e5" id="u2ea997e5"><span data-lake-id="ua35b1d94" id="ua35b1d94">​</span><br></p>
  <p data-lake-id="u4f6f83a5" id="u4f6f83a5"><span data-lake-id="u9719a904" id="u9719a904">B树是一种平衡的多叉树，通常我们说m阶的B树，它必须满足如下条件：</span></p>
  <ul list="ufc7bf8ef">
   <li fid="u2043768c" data-lake-id="uf12678e4" id="uf12678e4"><span data-lake-id="u4c13c4b0" id="u4c13c4b0">每个节点最多只有m个子节点。</span></li>
   <li fid="u2043768c" data-lake-id="u93210b05" id="u93210b05"><span data-lake-id="uf27ccecf" id="uf27ccecf">每个非叶子节点（除了根）具有至少⌈ m/2⌉子节点。</span></li>
   <li fid="u2043768c" data-lake-id="udd400903" id="udd400903"><span data-lake-id="u50eee527" id="u50eee527">如果根不是叶节点，则根至少有两个子节点。</span></li>
   <li fid="u2043768c" data-lake-id="u2a43f899" id="u2a43f899"><span data-lake-id="uac9692f1" id="uac9692f1">具有</span><span data-lake-id="u3f62fda0" id="u3f62fda0">k</span><span data-lake-id="u9fcff412" id="u9fcff412">个子节点的非叶节点包含</span><span data-lake-id="u627606ef" id="u627606ef">k</span><span data-lake-id="ud68ce2c9" id="ud68ce2c9"> </span><span data-lake-id="ub8847dcd" id="ub8847dcd">-1个键。</span></li>
   <li fid="u2043768c" data-lake-id="uc211cd2c" id="uc211cd2c"><span data-lake-id="ude976f65" id="ude976f65">所有叶子都出现在同一水平，没有任何信息（高度一致）。</span></li>
  </ul>
  <p data-lake-id="uaf6f688a" id="uaf6f688a"><span data-lake-id="ua5dd6f1a" id="ua5dd6f1a">​</span><br></p>
  <p data-lake-id="uddbd1ef1" id="uddbd1ef1"><img src="https://cdn.nlark.com/yuque/0/2023/png/5378072/1688460675265-1237e32b-f43d-4ba4-aba6-975026b9949b.png?x-oss-process=image%2Fwatermark%2Ctype_d3F5LW1pY3JvaGVp%2Csize_83%2Ctext_SmF2YSA4IEd1IFA%3D%2Ccolor_FFFFFF%2Cshadow_50%2Ct_80%2Cg_se%2Cx_10%2Cy_10"></p>
  <p data-lake-id="u015ac906" id="u015ac906"><span data-lake-id="u8bc4d3e5" id="u8bc4d3e5">​</span><br></p>
  <p data-lake-id="u7d84dc2c" id="u7d84dc2c"><span data-lake-id="u20adbd4a" id="u20adbd4a">B树具有以下特点：</span></p>
  <ol list="u3245869f">
   <li fid="uce92986c" data-lake-id="u28bd1c0f" id="u28bd1c0f"><span data-lake-id="u177cdd6e" id="u177cdd6e">B树是一种</span><span data-lake-id="u1f2cbeff" id="u1f2cbeff">多路搜索树</span><span data-lake-id="ubd99380d" id="ubd99380d">，每个节点可以包含多个子节点。相对于二叉搜索树，B树可以存储更多的关键字和子节点，从而降低了树的高度，减少了磁盘访问次数。</span></li>
   <li fid="uce92986c" data-lake-id="udcaac3a9" id="udcaac3a9"><span data-lake-id="u682dbc63" id="u682dbc63">B树通过在插入和删除操作时进行节点分裂和合并，保持树的平衡状态。这样可以确保树的高度始终保持在可接受的范围内，保证了较快的查询性能。</span></li>
   <li fid="uce92986c" data-lake-id="u1fd303d5" id="u1fd303d5"><span data-lake-id="ub5fc0635" id="ub5fc0635">B树的节点中的关键字按照升序排列</span><span data-lake-id="u5f507031" id="u5f507031">，使得范围查询操作更加高效。通过遍历树中的叶子节点，可以顺序获取连续的数据。</span></li>
   <li fid="uce92986c" data-lake-id="u3d8427e6" id="u3d8427e6"><span data-lake-id="uf6913b78" id="uf6913b78">B树的关键字和数据项可以存储在叶子节点和非叶子节点上。并且每个关键字出现且只出现在一个节点中。</span></li>
   <li fid="uce92986c" data-lake-id="u667f122b" id="u667f122b"><span data-lake-id="u8e31b972" id="u8e31b972">B树的搜索可能在非叶子节点上结束，他的搜索性能相当于在关键字全集中做二分查找。</span></li>
  </ol>
  <p data-lake-id="u6b44fb29" id="u6b44fb29"><br></p>
  <p data-lake-id="ubf5ed238" id="ubf5ed238"><span data-lake-id="u09c66efa" id="u09c66efa">B+树是B-树的变体，也是一种多路搜索树, 它与 B- 树的不同之处在于以下三个方面</span></p>
  <p data-lake-id="u12cfea77" id="u12cfea77"><span data-lake-id="ud1afdb45" id="ud1afdb45">​</span><br></p>
  <ol list="ue92230b1">
   <li fid="uc97a8a68" data-lake-id="u7ab50d63" id="u7ab50d63"><span data-lake-id="u56737289" id="u56737289">数据存储位置：在B树中，数据项存储在叶子节点和非叶子节点上，而在B+树中，数据项只存储在叶子节点上。非叶子节点只包含键值信息。</span></li>
   <li fid="uc97a8a68" data-lake-id="ucd1b5006" id="ucd1b5006"><span data-lake-id="uffeb1791" id="uffeb1791">叶子节点指针：B树的叶子节点之间没有指针连接，每个叶子节点独立存储数据项。而B+树的叶子节点通过指针连接成一个链表，可以方便地进行范围查询。</span></li>
  </ol>
  <p data-lake-id="u38c1fa21" id="u38c1fa21"><span data-lake-id="ua9892f3b" id="ua9892f3b">​</span><br></p>
  <p data-lake-id="u79cfc4ae" id="u79cfc4ae"><img src="https://cdn.nlark.com/yuque/0/2023/png/5378072/1693117444889-9b121593-a91f-478c-9413-9e40af0298f8.png?x-oss-process=image%2Fwatermark%2Ctype_d3F5LW1pY3JvaGVp%2Csize_39%2Ctext_SmF2YSA4IEd1IFA%3D%2Ccolor_FFFFFF%2Cshadow_50%2Ct_80%2Cg_se%2Cx_10%2Cy_10"></p>
  <p data-lake-id="u11e3e4eb" id="u11e3e4eb"><br></p>
  <p data-lake-id="ua9ebf998" id="ua9ebf998"><span data-lake-id="udc8b21c3" id="udc8b21c3">由于B+树的叶子节点之间通过双向指针链接进而形成了链表，所以B+树在范围查询时更加高效。通过遍历叶子节点链表，可以获取连续的数据项，而不需要回溯到非叶子节点。</span></p>
  <p data-lake-id="ub1970ab5" id="ub1970ab5"><br></p>
  <p data-lake-id="u45c2d886" id="u45c2d886"><span data-lake-id="ub1b81845" id="ub1b81845">​</span><br></p>
  <p data-lake-id="u33992585" id="u33992585"><span data-lake-id="u2fef63db" id="u2fef63db">​</span><br></p>
  <p data-lake-id="u57d6441b" id="u57d6441b"><span data-lake-id="u59f3fd4a" id="u59f3fd4a"><br><br></span></p>
 </body>
</html>